package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC3673 {

    static class Solution {
        /**
         * @param n:         the number of courses
         * @param relations: the relationship between all courses
         * @return: ehe minimum number of semesters required to complete all courses
         */
        public int minimumSemesters(int n, int[][] relations) {
            Map<Integer, Node> graph = new HashMap<>();
            for (int[] r : relations) {
                int from = r[0];
                int to = r[1];

                if (!graph.containsKey(from)) {
                    graph.put(from, new Node(from));
                }

                if (!graph.containsKey(to)) {
                    graph.put(to, new Node(to));
                }

                graph.get(to).in++;
                graph.get(from).nexts.add(graph.get(to));
            }


            Set<Integer> visited = new HashSet<>();
            Queue<Node> q = new LinkedList<>();

            int ans = 0;
            for (int k : graph.keySet()) {
                if (graph.get(k).in == 0) {
                    q.add(graph.get(k));
                    visited.add(k);

                }
            }

            if(q.isEmpty()) return -1;

            while (!q.isEmpty()) {
                int size = q.size();
                ans++;
                for (int i = 0; i < size; i++) {
                    Node cur = q.poll();

                    List<Node> nexts = cur.nexts;
                    for (Node next : nexts) {
                        if (visited.contains(next.data)) return -1;

                        if (--next.in == 0) {
                            q.add(next);
                            visited.add(next.data);
                        }
                    }
                }
            }

            return ans;
        }

        static class Node { //图的节点定义
            int data;
            int in;
            List<Node> nexts;

            public Node(int d) {
                data = d;
                in = 0;
                nexts = new ArrayList<>();
            }
        }
    }

    public static void main(String[] args) {
        int[][] arr1 = {{1, 2}, {2, 3}, {2, 4}};
        int[][] arr2 = {{1, 2}, {2, 3}, {2, 4}, {3, 4}};
        int[][] arr3 = {{1, 2}, {2, 1}};

        System.out.println();

        Solution obj = new Solution();
        System.out.println(obj.minimumSemesters(4,arr1));
        System.out.println(obj.minimumSemesters(4,arr2));
        System.out.println(obj.minimumSemesters(2, arr3));
        System.out.println(obj.minimumSemesters(20, new int[][]{{18, 6}, {15, 3}, {11, 3}, {17, 4}, {4, 11}, {8, 3}, {1, 16}, {18, 4}, {19, 6}, {5, 11}, {4, 1}, {9, 16}, {14, 5}, {12, 20}, {8, 9}, {5, 4}, {15, 2}, {10, 2}, {13, 4}, {6, 9}}));
    }
}


/*
20
[[18,6],[15,3],[11,3],[17,4],[4,11],[8,3],[1,16],[18,4],[19,6],[5,11],[4,1],[9,16],[14,5],[12,20],[8,9],[5,4],[15,2],[10,2],[13,4],[6,9]]
输出数据
-1
期望答案
5
 */

/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3673 · 并行课程
算法
中等
通过率
48%

题目
题解5
笔记
讨论
排名
记录
描述
在本题中，存在 n 个课程。其编号为 1 到 n。

同时存在一个二维数组 relations。其内部每个数组均包含两个课程。其中第一个课程为第二个课程的前置课程。即学习数组中第二个课程之前必须先学习数组中第一个课程。

在一个学期中，你可以学习任何数量的课程，前提是你已经在之前的学期中学完了该课程的所有前置课程。

返回学习全部课程的最少学期，如果无法完成全部课程的学习，返回 -1。

样例
样例 1

输入：

4
[[1,2],[2,3],[2,4]]
输出：

3
解释：

第一学期：学习 1
第二学期：学习 2
第三学期：学习 3、4
样例 2

输入：

4
[[1,2],[2,3],[2,4],[3,4]]
输出：

4
样例 3

输入：

2
[[1,2],[2,1]]
输出：

-1
标签
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
6/24
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
